#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

//int main()
//{
//	int a;
//	int b[100] = { 0 };
//	int c;
//	int k = 0;
//	cin >> a;
//	for (int i = 0; i < a; i++)
//	{
//		cin >> b[i];
//	}
//	cin >> c;
//	for (int i = 0; i < a; i++)
//	{
//		if (b[i] == c)
//		{
//			k++;
//		}
//	}
//	cout << k << endl;
//	system("pause");
//	return 0;
//}

//int main()
//{
//	printf("printf(\"hello world!\\n\";)\n");
//	printf("cout<<\"hellow world\"<<endl;\n");
//	system("pause");
//	return 0;
//}

//#include <math.h>
//int i_print()
//{
//	int num = 0;
//	for (int i = 1; i <= 999; i++)
//	{
//		int n;
//		for (n = 2; n < sqrt(i); n++)
//		{
//			if (i % n == 0)
//			{
//				break;
//			}
//		}
//		if (n > sqrt(i))
//		{
//			num++;
//		}
//	}
//	return num;
//}
//
//int main()
//{
//	int num = 0;
//	num = i_print();
//	cout << num << endl;
//	system("pause");
//	return 0;
//}

//int main()
//{
//	int a;
//	cin >> a;
//	int arr[1000];
//	int arr2[1000] = { 0 };
//	for (int i = 0; i < a; i++)
//	{
//		cin >> arr[i];
//		arr2[arr[i]]++;
//	}
//	for (int i = 0; i <= 1000; i++)
//	{
//		if (arr2[i] != 0)
//		{
//			cout << i << " ";
//		}
//	}
//	cout << endl;
//	system("pause");
//	return 0;
//}

#include <string>
#include <list>
//int main()
//{
//	list<int> l;
//	int a;
//	cin >> a;
//	for (int i = 0; i < a; i++)
//	{
//		int c;
//		cin >> c;
//		l.push_back(c);
//	}
//	int c;
//	cin >> c;
//	for (list<int>::iterator it = l.begin(); it != l.end(); )
//	{
//		if ((*it) == c)
//		{
//			l.erase(it++);
//		}
//		else
//		{
//			it++;
//		}
//	}
//	for (list<int>::iterator lit = l.begin(); lit != l.end(); lit++)
//	{
//		cout << *lit << endl;
//	}
//	system("pause");
//	return 0;
//}

//typedef struct P
//{
//	int a;
//	struct P* next;
//}P;
//
//int main()
//{
//	P* p = NULL;
//	int a;
//	P* pend = p;
//	scanf("%d", &a);
//	for (int i = 0; i < a; i++)
//	{
//		P* pp = (P*)malloc(sizeof(P));
//		scanf("%d", &pp->a);
//		pp->next = NULL;
//		if (p == NULL)
//		{
//			p = pp;
//			pend = pp;
//
//		}
//		else
//		{
//			pend->next = pp;
//			pend = pend->next;
//		}
//	}
//	int b;
//	scanf("%d", &b);
//	P* firstp = p;
//	while (firstp)
//	{
//		if (firstp->a == b && firstp == p)
//		{
//			P* firstpp = p->next;
//			free(p);
//			firstp = firstpp;
//			p = firstp;
//		}
//		else if (firstp->next != NULL && firstp->next->a == b)
//		{
//			P* firstpp = firstp->next;
//			firstp->next = firstpp->next;
//			free(firstpp);
//		}
//		else
//		{
//			firstp = firstp->next;
//		}
//	}
//	firstp = p;
//	while (firstp)
//	{
//		printf("%d ", firstp->a);
//		firstp = firstp->next;
//	}
//	system("pause");
//	return 0;
//}

//class Time
//{
//public:
//	Time()
//	{
//		this->m_Year = 0;
//		this->m_Month = 0;
//		this->m_Day = 0;
//	}
//	void printTime()
//	{
//		cout << this->m_Day << "/" << this->m_Month << "/" << this->m_Year << endl;
//	}
//	void cinTime(int year, int month, int day)
//	{
//		this->m_Year = year;
//		this->m_Month = month;
//		this->m_Day = day;
//	}
//private:
//	int m_Month;
//	int m_Day;
//	int m_Year;
//};
//
//int main()
//{
//	Time m_time;
//	int year, month, day;
//	cin >> year >> month >> day;
//	m_time.cinTime(year, month, day);
//	m_time.printTime();
//	system("pause");
//	return 0;
//}

//int main()
//{
//	int k;
//	scanf("%d", &k);
//	int arr[40];
//	int i = 0;
//	while (k)
//	{
//		arr[i] = k % 6;
//		i++;
//		k /= 6;
//	}
//	for (i--; i >= 0; i--)
//	{
//		printf("%d", arr[i]);
//	}
//	return 0;
//}

//int main()
//{
//	int h, m, k;
//	scanf("%d %d %d", &h, &m, &k);
//	if (m + k >= 60)
//	{
//		h += (m + k) / 60;
//		m = (m + k) % 60;
//	}
//	if (h > 23)
//	{
//		h %= 24;
//	}
//	printf("%02d:%02d\n", h, m);
//	system("pause");
//	return 0;
//}

//int main()
//{
//	int n, m;
//	scanf("%d %d", &m, &n);
//	int m1 = m;
//	int n1 = n;
//	int k = 0;
//	while (n)
//	{
//		k = m % n;
//		m = n;
//		n = k;
//	}
//	int max = m;
//	int min = (m1 * n1) / max;
//	printf("%d\n", min + max);
//	system("pause");
//	return 0;
//}

//int main()
//{
//	int c;
//	int k = 0;
//	int n = 0;
//	cin >> c;
//	while (c)
//	{
//		if (c % 10 % 2 == 0)
//		{
//			k += 0*pow(10, n);
//		}
//		else if (c % 10 % 2 == 1)
//		{
//			k += pow(10, n);
//		}
//		n++;
//		c /= 10;
//	}
//	cout << k << endl;
//	system("pause");
//	return 0;
//}